package 排序算法.堆排序;

import java.util.Arrays;

/**
 * 堆排序
 * 时间复杂度：O(n * log2 n)
 * 空间复杂度：O(1)
 * 稳定
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr= {8,9,58,5,6,3,5,87,0,5,5};
        heapSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        //每次找到最大的值放到根节点，即数组的第一位置
        heapify(arr, arr.length);
        for (int i = arr.length - 1; i >= 0 ; i--) {
            //找到最大值后，在交换第一个位置的最大值到数组的最后一个位置，每次最后的位置都要改变即减一
            swap(arr, 0 , i);
            //接着在找第二个、第三个......个，并每次要排除已经得出的最大的值，因此数组的长度要动态的改变（i的值）
            heapify(arr, i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        //交换数组中，i和j位置的索引的值
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void heapify(int[] arr, int len) {
        //从数组的最后一个元素开始，组成一个堆（字节点的值都比其根节点的值要小），最后一个数字，即完全二叉树的最后一个叶子节点的值
        for (int i =  len - 1; i >= 0; i--) {
            shiftDown(arr,i,len);
        }

    }

    private static void shiftDown(int[] arr, int k, int len) {
        //判断该节点是否有左孩子，有左孩子取出该下标
        while(leftChild(k) < len){
            int j = leftChild(k);
            //判断该节点是否有右孩子，有的话在比较左右孩子的大小，右孩子大j就为右孩子的下标
            if (rightChild(k) < len && arr[j] < arr[j + 1]){
                j = rightChild(k);
            }
            //最后比较根节点和其最大孩子的大小，比根节点大就交换顺序并把k的值定义为j,在向下继续比较，将最大的值找到并放到根节点的位置
            if (arr[k] < arr[j]){
                swap(arr,k,j);
                k = j;
            }else {
                break;
            }
        }

    }

    private static int rightChild(int k) {
        //返回有孩子的下标
        return 2 * k + 2;
    }

    private static int leftChild(int k) {
        //返回左孩子的小标
        return  2 * k + 1;
    }
}
